Package-level declarations

This package contains most of the string measure implementations.

Algorithms

Edit-based measures (Levenshtein, LCS, Damerau-Levenshtein, etc.)

Levenshtein

The Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into the other.

It is a metric string distance.

This class implements the dynamic programming approach with two arrays, which has a space requirement \(O(n)\), and computation cost \(O(m \times n)\).

Example

val levenshtein = Levenshtein()

println(levenshtein.distance("My string", "My \$tring")) // prints 1.0

Damerau-Levenshtein

Similar to the Levenshtein distance, the Damerau-Levenshtein distance with transposition (also sometimes calls unrestricted Damerau-Levenshtein distance) is the minimum number of operations needed to transform one string into the other, where an operation is defined as an insertion, deletion, or substitution of a single character, or a transposition of two adjacent characters.

It is a metric string distance.

This class implements the dynamic programming approach, which has a space requirement \(O(m \times n)\), and computation cost \(O(m \times n)\).

This is not to be confused with the optimal string alignment distance, which is an extension where no substring can be edited more than once.

Example

val damerau = DamerauLevenshtein()

println(damerau.distance("ABCDEF", "ABDCEF")) // prints 1.0

// 2 substitutions
println(damerau.distance("ABCDEF", "BACDFE")) // prints 2.0

// 1 deletion
println(damerau.distance("ABCDEF", "ABCDE")) // prints 1.0
println(damerau.distance("ABCDEF", "BCDEF")) // prints 1.0
println(damerau.distance("ABCDEF", "ABCGDEF")) // prints 1.0

// All different
println(damerau.distance("ABCDEF", "POIU")) // prints 6.0

// Transpose
println(damerau.distance("CA", "ABC")) // prints 2.0

Optimal String Alignment

The Optimal String Alignment distance variant of Damerau-Levenshtein distance (sometimes called the restricted edit distance) computes the number of edit operations needed to make the strings equal under the condition that no substring is edited more than once, whereas the true the Damerau-Levenshtein distance presents no such restriction. The difference from the algorithm for the Levenshtein distance is the addition of one recurrence for the transposition operations.

It is not a metric string distance.

This class implements the dynamic programming approach, which has a space requirement \(O(m \times n)\), and computation cost \(O(m \times n)\).

Example

val osa = OptimalStringAlignment()

println(osa.distance("ABCDEF", "ABDCEF")) // prints 1.0

// 2 substitutions
println(osa.distance("ABCDEF", "BACDFE")) // prints 2.0

// 1 deletion
println(osa.distance("ABCDEF", "ABCDE")) // prints 1.0
println(osa.distance("ABCDEF", "BCDEF")) // prints 1.0
println(osa.distance("ABCDEF", "ABCGDEF")) // prints 1.0

// All different
println(osa.distance("ABCDEF", "POIU")) // prints 6.0

println(osa.distance("CA", "ABC")) // prints 3.0

Longest Common Subsequence

The Longest Common Subsequence (LCS) problem consists in finding the longest subsequence common to two (or more) sequences. It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

It is used by the diff utility, by Git for reconciling multiple changes, etc.

The LCS distance is equivalent to the Levenshtein distance when only insertion and deletion is allowed (no substitution), or when the cost of the substitution is the double of the cost of an insertion or deletion.

It is a metric string distance.

This class implements the dynamic programming approach with two arrays, which has a space requirement \(O(n)\), and computation cost \(O(m \times n)\)^[a].

Example

val lcs = LCS()

println(lcs.distance("AGCAT", "GAC")) // prints 4.0

println(lcs.distance("AGCAT", "AGCT")) // prints 1.0

Shingles (n-gram) based similarity and distance

A few algorithms work by converting strings into sets of n-grams (sequences of n characters, also sometimes called k-shingles). The similarity or distance between the strings is then the similarity or distance between the sets.

Some of them, like the Jaccard index, consider strings as sets of shingles, and don't consider the number of occurrences of each shingle. Others, like cosine similarity, work using what is sometimes called the profile of the strings, which takes into account the number of occurrences of each shingle.

For these algorithms, another use case is possible when dealing with large datasets:

1. Compute the set or profile representation of all the strings

2. Compute the similarity between sets or profiles

Jaro-Winkler

Jaro-Winkler is a string distance that was developed in the area of record linkage (duplicate detection), as defined by Winkler^[1]. The Jaro–Winkler distance metric is designed and best suited for short strings such as person names, and to detect transposition typos.

Jaro-Winkler computes the similarity between 2 strings, and the returned value lies in the interval \([0.0, 1.0]\). It is (roughly) a variation of ca.solostudios.stringsimilarity.normalized.DamerauLevenshtein, where the transposition of 2 close characters is considered less important than the transposition of 2 characters that are far from each other. Jaro-Winkler penalizes additions or substitutions that cannot be expressed as transpositions.

Example

val jaroWinkler = JaroWinkler()

// substitution of s and t
println(jaroWinkler.similarity("My string", "My tsring")) // prints 0.9740740656852722

// substitution of s and n
println(jaroWinkler.similarity("My string", "My ntrisg")) // prints 0.8962963223457336

N-Gram

N-Gram similarity/distance is a distance used to measure the similarity of two strings, that always lies in the range \([0.0, 1.0]\).

The algorithm uses affixing with special character '\0' to increase the weight of first characters. The normalization is achieved by dividing the total similarity score the original length of the longest word.

Example

val twogram = NGram(2)
println(twogram.distance("ABCD", "ABTUIO")) // prints 0.583333

val s1 = "Adobe CreativeSuite 5 Master Collection from cheap 4zp"
val s2 = "Adobe CreativeSuite 5 Master Collection from cheap d1x"
val ngram = NGram(4)
println(ngram.distance(s1, s2)) // prints 0.97222

Shingle (n-gram) based algorithms

A few algorithms work by converting strings into sets of n-grams (sequences of n characters, also sometimes called k-shingles). The similarity or distance between the strings is then the similarity or distance between the sets.

Note: although it may seem it is, the N-Gram similarity/distance is not shingle-based.

The cost for computing these similarities and distances is mainly dominated by k-shingling (converting the strings into sequences of k characters).

There are typically two use cases for these algorithms:

1. Directly compute the distance between strings:

   val dig = QGram(2)
   
   // AB BC CD CE
   // 1  1  1  0
   // 1  1  0  1
   // Total: 2
   
   println(dig.distance("ABCD", "ABCE")) // prints 2

   Content copied to clipboard

2. For large datasets, pre-compute the profile of all strings. The similarity can then be computed between profiles:

   /**
    * Example of computing cosine similarity with pre-computed profiles.
    */
   val s1 = "My first string"
   val s2 = "My other string..."
   
   // Let's work with sequences of 2 characters...
   val cosine = new Cosine(2)
   
   // Pre-compute the profile of strings
   val profile1 = cosine.profile(s1)
   val profile2 = cosine.profile(s2)
   
   // ...
   
   println(cosine.similarity(profile1, profile2)) // prints 0.516185

   Content copied to clipboard

Pay attention, this only works if the same KShingling object is used to parse all input strings!

Q-Gram

Q-gram distance, as defined by Ukkonen in "Approximate string-matching with q-grams and maximal matches"^[3].

The distance between two strings is defined as the L1 norm of the difference of their profiles (the number of occurences of each n-gram): \(\sum_{i=1}^n \lVert \vec{v1_i} - \vec{v2_i} \rVert\). Q-gram distance is a lower bound on the ca.solostudios.stringsimilarity.normalized.Levenshtein distance, but can be computed in \(O(m + n)\) time, whereas the ca.solostudios.stringsimilarity.normalized.Levenshtein distance requires \(O(m \times n)\) time.

Cosine similarity

The similarity between the two strings is the cosine of the angle between these two vector representation, and is computed as \(\frac{\vec{v_1} \cdot \vec{v_2}}{\lVert\vec{v_1}\rVert \times \lVert\vec{v_2}\rVert}\).

Jaccard index

Like Q-Gram distance, the input strings are first converted into sets of n-grams (sequences of n characters, also called k-shingles), but this time the cardinality of each n-gram is not taken into account. Each input string is simply a set of n-grams. The Jaccard index is then computed as \(\frac{\lVert V_1 \cap V_2 \rVert}{\lVert V_1 \cup V_2 \rVert}\).

Jaccard index is a metric distance.

Sørensen-Dice coefficient

Similar to the Jaccard index, but this time the similarity is computed as \(\frac{2 \times \lVert V_1 \cap V_2 \rVert}{\lVert V_1 \rVert + \lVert V_2 \rVert}\).

Ratcliff-Obershelp

Ratcliff/Obershelp Pattern Recognition, also known as Gestalt Pattern Matching, is a string-matching algorithm for determining the similarity of two strings. It was developed in 1983 by John W. Ratcliff and John A. Obershelp and published in the Dr. Dobb's Journal in July 1988^[4].

Ratcliff/Obershelp computes the similarity between 2 strings, and the returned value lies in the interval \([0.0, 1.0]\).

Example

val ratcliffObershelp = RatcliffObershelp()

// substitution of s and t
println(ratcliffObershelp.similarity("My string", "My tsring")) // prints 0.8888888888888888

// substitution of s and n
println(ratcliffObershelp.similarity("My string", "My ntrisg")) // prints 0.7777777777777778

Experimental

Sift4

Sift4 is a general purpose string distance algorithm inspired by JaroWinkler and ca.solostudios.stringsimilarity.normalized.LCS. It was developed to produce a distance measure that matches as close as possible to the human perception of string distance. Hence, it takes into account elements like character substitution, character distance, longest common subsequence etc.

It was developed using experimental testing, and without theoretical background.

Example

val s1 = "This is the first string"
val s2 = "And this is another string"
val sift4 = Sift4(maxOffset = 5)

val expectedResult = 11.0
val result = sift4.distance(s1, s2)

assertEquals(expectedResult, result, 0.0)

Notes

References

References